package simple;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
 *
 * 实现 MyStack 类：
 *
 * void push(int x) 将元素 x 压入栈顶。
 * int pop() 移除并返回栈顶元素。
 * int top() 返回栈顶元素。
 * boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
 * 链接：https://leetcode-cn.com/problems/implement-stack-using-queues
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class ImplementStackUsingQueues {

}
/**
 * 用两个队列（先进先出）实现一个栈（后进先出）
 * 我们要考虑的问题就是如何做到出队的时候 让最后一个元素先出
 * 可以先将队列中的其他元素放到另外一个队列，将最后一个元素取出
 * (实际上 这道题也可以只用一个队列实现，即我们在出队时，将其他元素加入到队列本身，给最后一个元素让出位置)
 * */
class MyStack {
    // 队列1 作为存放队列
    Deque<Integer> deque1 = new ArrayDeque<>();

    // 队列2 作为出队队列
    Deque<Integer> deque2 = new ArrayDeque<>();
    public MyStack() {

    }

    public void push(int x) {
        deque1.offer(x);
    }

    public int pop() {
        while(deque1.size() != 1){
            deque2.offer(deque1.poll());
        }
        int val = deque1.poll();
        Deque<Integer> tempDeque = deque1;
        deque1 = deque2;
        deque2 = tempDeque;
        return val;
    }

    public int top() {
        int val = 0;
        while(!deque1.isEmpty()){
            val = deque1.poll();
            deque2.offer(val);
        }
        Deque<Integer> tempDeque = deque1;
        deque1 = deque2;
        deque2 = tempDeque;
        return val;
    }

    public boolean empty() {
        return deque1.isEmpty();
    }
}
